using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Linq;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;

namespace New.Data
{
    /// <summary>
    /// 高性能红黑树实现
    /// 使用值类型节点、数组存储、位操作、内联优化和路径缓存等技术优化性能
    ///红黑树实现了完整的增删改查操作，包括：
    ///Add：添加或更新键值对
    ///Remove：移除指定键的节点
    ///TryGetValue：获取指定键的值
    ///ContainsKey：检查是否包含指定键
    ///ForEach：遍历树中的所有键值对
    /// ___________________________
    /// - IsEmpty和Height属性，方便快速获取树的状态
     ///GetBalanceFactor方法，用于评估树的平衡程度
      ///  TryGetNextKey和TryGetPreviousKey方法，支持查找相邻键
       /// ToDictionary方法，支持与Dictionary类型的转换
    /// </summary>
    /// <typeparam name="TKey">键类型</typeparam>
    /// <typeparam name="TValue">值类型</typeparam>
    public class Data_RBTree<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>> where TKey : IComparable<TKey>
    {
        // 常量定义
        private const int DEFAULT_CAPACITY = 16;
        private const int RED = 0;
        private const int BLACK = 1;
        private const int NULL_NODE = -1;

        // 节点结构体 - 使用值类型减少堆分配
        private struct Node
        {
            public TKey Key;
            public TValue Value;
            public int Left; // 左子节点索引
            public int Right; // 右子节点索引
            public int Parent; // 父节点索引
            public int Color; // 使用整数位表示颜色，避免布尔类型开销
        }

        // 数组存储 - 提高内存局部性
        private Node[] _nodes;
        private int _count;
        private int _root;
        private int _freeList;
        private int _capacity;

        // 路径缓存 - 避免重复遍历
        private readonly Stack<int> _pathCache;

        /// <summary>
        /// 构造函数
        /// </summary>
        public Data_RBTree() : this(DEFAULT_CAPACITY)
        {
        }

        /// <summary>
        /// 带初始容量的构造函数
        /// </summary>
        public Data_RBTree(int capacity)
        {
            _capacity = Math.Max(capacity, DEFAULT_CAPACITY);
            _nodes = new Node[_capacity];
            _root = NULL_NODE;
            _count = 0;
            _freeList = NULL_NODE;
            _pathCache = new Stack<int>(_capacity);
        }

        /// <summary>
        /// 获取元素数量
        /// </summary>
        public int Count => _count;

        /// <summary>
        /// 判断树是否为空
        /// </summary>
        public bool IsEmpty => _count == 0;

        /// <summary>
        /// 获取树的高度
        /// </summary>
        public int Height => GetHeight(_root);

        /// <summary>
        /// 计算树的高度
        /// </summary>
        private int GetHeight(int node)
        {
            if (node == NULL_NODE)
            {
                return 0;
            }

            int leftHeight = GetHeight(_nodes[node].Left);
            int rightHeight = GetHeight(_nodes[node].Right);

            return Math.Max(leftHeight, rightHeight) + 1;
        }

        /// <summary>
        /// 清空树
        /// </summary>
        public void Clear()
        {
            _root = NULL_NODE;
            _count = 0;
            _freeList = NULL_NODE;
            Array.Clear(_nodes, 0, _capacity);
        }

        /// <summary>
        /// 添加或更新键值对
        /// </summary>
        /// <param name="key">要添加的键</param>
        /// <param name="value">要添加的值</param>
        /// <exception cref="ArgumentNullException">当key为null时抛出</exception>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Add(TKey key, TValue value)
        {
            if (_root == NULL_NODE)
            {
                // 树为空，创建根节点
                _root = AllocateNode(key, value);
                _nodes[_root].Color = BLACK;
                return;
            }

            // 查找插入位置
            int current = _root;
            int parent = NULL_NODE;
            int comparison = 0;

            _pathCache.Clear();

            while (current != NULL_NODE)
            {
                _pathCache.Push(current);
                parent = current;
                comparison = key.CompareTo(_nodes[current].Key);

                if (comparison == 0)
                {
                    // 键已存在，更新值
                    _nodes[current].Value = value;
                    return;
                }

                current = comparison < 0 ? _nodes[current].Left : _nodes[current].Right;
            }

            // 创建新节点
            int newNode = AllocateNode(key, value);
            _nodes[newNode].Parent = parent;

            // 连接到父节点
            if (comparison < 0)
            {
                _nodes[parent].Left = newNode;
            }
            else
            {
                _nodes[parent].Right = newNode;
            }

            // 修复红黑树属性
            FixAfterInsertion(newNode);
        }

        /// <summary>
        /// 移除指定键的节点
        /// </summary>
        /// <param name="key">要移除的键</param>
        /// <returns>如果成功移除返回true，否则返回false</returns>
        /// <exception cref="ArgumentNullException">当key为null时抛出</exception>
        public bool Remove(TKey key)
        {
            int node = FindNode(key);
            if (node == NULL_NODE)
            {
                return false;
            }

            RemoveNode(node);
            
            // 当节点数量减少到一定程度时，考虑收缩容量以节省内存
            if (_count > 0 && _count < _capacity / 4)
            {
                TrimExcess();
            }
            
            return true;
        }

        /// <summary>
        /// 获取指定键的值
        /// </summary>
        public bool TryGetValue(TKey key, out TValue value)
        {
            int node = FindNode(key);
            if (node != NULL_NODE)
            {
                value = _nodes[node].Value;
                return true;
            }

            value = default;
            return false;
        }

        /// <summary>
        /// 检查是否包含指定键
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool ContainsKey(TKey key)
        {
            return FindNode(key) != NULL_NODE;
        }

        /// <summary>
        /// 查找节点
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int FindNode(TKey key)
        {
            int current = _root;

            while (current != NULL_NODE)
            {
                int comparison = key.CompareTo(_nodes[current].Key);
                if (comparison == 0)
                {
                    return current;
                }

                current = comparison < 0 ? _nodes[current].Left : _nodes[current].Right;
            }

            return NULL_NODE;
        }

        /// <summary>
        /// 查找节点并缓存路径
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int FindNodeWithPath(TKey key, bool cachePath = false)
        {
            int current = _root;

            if (cachePath)
            {
                _pathCache.Clear();
            }

            while (current != NULL_NODE)
            {
                if (cachePath)
                {
                    _pathCache.Push(current);
                }

                int comparison = key.CompareTo(_nodes[current].Key);
                if (comparison == 0)
                {
                    return current;
                }

                current = comparison < 0 ? _nodes[current].Left : _nodes[current].Right;
            }

            return NULL_NODE;
        }

        /// <summary>
        /// 分配新节点
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int AllocateNode(TKey key, TValue value)
        {
            int newNode;

            // 尝试从空闲列表获取节点
            if (_freeList != NULL_NODE)
            {
                newNode = _freeList;
                _freeList = _nodes[_freeList].Right; // 使用Right字段存储下一个空闲节点
            }
            else
            {
                // 检查是否需要扩容
                if (_count == _capacity)
                {
                    GrowCapacity();
                }

                newNode = _count;
                _count++;
            }

            // 初始化节点
            _nodes[newNode].Key = key;
            _nodes[newNode].Value = value;
            _nodes[newNode].Left = NULL_NODE;
            _nodes[newNode].Right = NULL_NODE;
            _nodes[newNode].Parent = NULL_NODE;
            _nodes[newNode].Color = RED; // 新节点默认为红色

            return newNode;
        }

        /// <summary>
        /// 扩容
        /// </summary>
         private void GrowCapacity()
        {
            int newCapacity = _capacity * 2;
            Node[] newNodes = new Node[newCapacity];
            Array.Copy(_nodes, newNodes, _capacity);
            _nodes = newNodes;
            _capacity = newCapacity;

            // 扩容后重新分配路径缓存，以适应更大的树深度
            // Stack<T>没有Capacity属性，使用Count来判断
            int estimatedMaxDepth = (int)Math.Log(newCapacity, 2) + 1; // 估计最大树深度
            if (_pathCache.Count < estimatedMaxDepth)
            {
                // 创建新的路径缓存
                Stack<int> newPathCache = new Stack<int>(estimatedMaxDepth);
                
                // 保存原有路径
                int[] tempArray = _pathCache.ToArray();
                _pathCache.Clear();
                
                // 按原顺序重新压入栈
                for (int i = tempArray.Length - 1; i >= 0; i--)
                {
                    newPathCache.Push(tempArray[i]);
                }
                
                // 替换为新的路径缓存
                _pathCache.Clear();
                while (newPathCache.Count > 0)
                {
                    _pathCache.Push(newPathCache.Pop());
                }
            }
        }

        /// <summary>
        /// 预分配容量，减少动态扩容次数
        /// </summary>
        /// <param name="capacity">预期容量</param>
        public void EnsureCapacity(int capacity)
        {
            if (capacity > _capacity)
            {
                int newCapacity = _capacity;
                while (newCapacity < capacity)
                {
                    newCapacity *= 2;
                }

                Node[] newNodes = new Node[newCapacity];
                Array.Copy(_nodes, newNodes, _capacity);
                _nodes = newNodes;
                _capacity = newCapacity;
            }
        }

        /// <summary>
        /// 插入后修复红黑树属性
        /// </summary>
        private void FixAfterInsertion(int x)
        {
            // 新插入的节点为红色
            _nodes[x].Color = RED;

            // 如果是根节点或父节点是黑色，不需要修复
            while (x != _root && _nodes[_nodes[x].Parent].Color == RED)
            {
                int parent = _nodes[x].Parent;
                int grandParent = _nodes[parent].Parent;

                if (parent == _nodes[grandParent].Left)
                {
                    // 父节点是祖父节点的左子节点
                    int uncle = _nodes[grandParent].Right;

                    // 情况1：叔叔节点是红色
                    if (uncle != NULL_NODE && _nodes[uncle].Color == RED)
                    {
                        _nodes[parent].Color = BLACK;
                        _nodes[uncle].Color = BLACK;
                        _nodes[grandParent].Color = RED;
                        x = grandParent;
                    }
                    else
                    {
                        // 情况2：叔叔节点是黑色，当前节点是右子节点
                        if (x == _nodes[parent].Right)
                        {
                            x = parent;
                            RotateLeft(x);
                            parent = _nodes[x].Parent;
                            grandParent = _nodes[parent].Parent;
                        }

                        // 情况3：叔叔节点是黑色，当前节点是左子节点
                        _nodes[parent].Color = BLACK;
                        _nodes[grandParent].Color = RED;
                        RotateRight(grandParent);
                    }
                }
                else
                {
                    // 父节点是祖父节点的右子节点
                    int uncle = _nodes[grandParent].Left;

                    // 情况1：叔叔节点是红色
                    if (uncle != NULL_NODE && _nodes[uncle].Color == RED)
                    {
                        _nodes[parent].Color = BLACK;
                        _nodes[uncle].Color = BLACK;
                        _nodes[grandParent].Color = RED;
                        x = grandParent;
                    }
                    else
                    {
                        // 情况2：叔叔节点是黑色，当前节点是左子节点
                        if (x == _nodes[parent].Left)
                        {
                            x = parent;
                            RotateRight(x);
                            parent = _nodes[x].Parent;
                            grandParent = _nodes[parent].Parent;
                        }

                        // 情况3：叔叔节点是黑色，当前节点是右子节点
                        _nodes[parent].Color = BLACK;
                        _nodes[grandParent].Color = RED;
                        RotateLeft(grandParent);
                    }
                }
            }

            // 确保根节点是黑色
            _nodes[_root].Color = BLACK;
        }

        /// <summary>
        /// 移除节点
        /// </summary>
        private void RemoveNode(int z)
        {
            // 保存原始颜色和替换节点
            int originalColor = _nodes[z].Color;
            int x;

            if (_nodes[z].Left == NULL_NODE)
            {
                // 没有左子节点
                x = _nodes[z].Right;
                Transplant(z, _nodes[z].Right);
            }
            else if (_nodes[z].Right == NULL_NODE)
            {
                // 没有右子节点
                x = _nodes[z].Left;
                Transplant(z, _nodes[z].Left);
            }
            else
            {
                // 有两个子节点，找到后继节点
                int y = Minimum(_nodes[z].Right);
                originalColor = _nodes[y].Color;
                x = _nodes[y].Right;

                if (_nodes[y].Parent == z)
                {
                    // 后继节点是z的直接右子节点
                    if (x != NULL_NODE)
                    {
                        _nodes[x].Parent = y;
                    }
                }
                else
                {
                    // 后继节点不是z的直接右子节点
                    Transplant(y, _nodes[y].Right);
                    _nodes[y].Right = _nodes[z].Right;
                    if (_nodes[y].Right != NULL_NODE)
                    {
                        _nodes[_nodes[y].Right].Parent = y;
                    }
                }

                // 用后继节点替换z
                Transplant(z, y);
                _nodes[y].Left = _nodes[z].Left;
                _nodes[_nodes[y].Left].Parent = y;
                _nodes[y].Color = _nodes[z].Color;
            }

            // 如果原始颜色是黑色，需要修复红黑树属性
            if (originalColor == BLACK && x != NULL_NODE)
            {
                FixAfterDeletion(x);
            }

            // 回收节点
            RecycleNode(z);
        }

        /// <summary>
        /// 删除后修复红黑树属性
        /// </summary>
        private void FixAfterDeletion(int x)
        {
            while (x != _root && GetColor(x) == BLACK)
            {
                if (x == _nodes[_nodes[x].Parent].Left)
                {
                    // x是左子节点
                    int w = _nodes[_nodes[x].Parent].Right; // 兄弟节点

                    // 情况1：兄弟节点是红色
                    if (GetColor(w) == RED)
                    {
                        _nodes[w].Color = BLACK;
                        _nodes[_nodes[x].Parent].Color = RED;
                        RotateLeft(_nodes[x].Parent);
                        w = _nodes[_nodes[x].Parent].Right;
                    }

                    // 情况2：兄弟节点的两个子节点都是黑色
                    if (GetColor(_nodes[w].Left) == BLACK && GetColor(_nodes[w].Right) == BLACK)
                    {
                        _nodes[w].Color = RED;
                        x = _nodes[x].Parent;
                    }
                    else
                    {
                        // 情况3：兄弟节点的右子节点是黑色
                        if (GetColor(_nodes[w].Right) == BLACK)
                        {
                            _nodes[_nodes[w].Left].Color = BLACK;
                            _nodes[w].Color = RED;
                            RotateRight(w);
                            w = _nodes[_nodes[x].Parent].Right;
                        }

                        // 情况4：兄弟节点的右子节点是红色
                        _nodes[w].Color = _nodes[_nodes[x].Parent].Color;
                        _nodes[_nodes[x].Parent].Color = BLACK;
                        _nodes[_nodes[w].Right].Color = BLACK;
                        RotateLeft(_nodes[x].Parent);
                        x = _root; // 结束循环
                    }
                }
                else
                {
                    // x是右子节点
                    int w = _nodes[_nodes[x].Parent].Left; // 兄弟节点

                    // 情况1：兄弟节点是红色
                    if (GetColor(w) == RED)
                    {
                        _nodes[w].Color = BLACK;
                        _nodes[_nodes[x].Parent].Color = RED;
                        RotateRight(_nodes[x].Parent);
                        w = _nodes[_nodes[x].Parent].Left;
                    }

                    // 情况2：兄弟节点的两个子节点都是黑色
                    if (GetColor(_nodes[w].Right) == BLACK && GetColor(_nodes[w].Left) == BLACK)
                    {
                        _nodes[w].Color = RED;
                        x = _nodes[x].Parent;
                    }
                    else
                    {
                        // 情况3：兄弟节点的左子节点是黑色
                        if (GetColor(_nodes[w].Left) == BLACK)
                        {
                            _nodes[_nodes[w].Right].Color = BLACK;
                            _nodes[w].Color = RED;
                            RotateLeft(w);
                            w = _nodes[_nodes[x].Parent].Left;
                        }

                        // 情况4：兄弟节点的左子节点是红色
                        _nodes[w].Color = _nodes[_nodes[x].Parent].Color;
                        _nodes[_nodes[x].Parent].Color = BLACK;
                        _nodes[_nodes[w].Left].Color = BLACK;
                        RotateRight(_nodes[x].Parent);
                        x = _root; // 结束循环
                    }
                }
            }

            // 确保节点是黑色
            if (x != NULL_NODE)
            {
                _nodes[x].Color = BLACK;
            }
        }

        /// <summary>
        /// 获取节点颜色，NULL_NODE视为黑色
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int GetColor(int node)
        {
            return node == NULL_NODE ? BLACK : _nodes[node].Color;
        }

        /// <summary>
        /// 左旋转
        /// </summary>
        private void RotateLeft(int x)
        {
            int y = _nodes[x].Right;

            // 将y的左子节点设为x的右子节点
            _nodes[x].Right = _nodes[y].Left;
            if (_nodes[y].Left != NULL_NODE)
            {
                _nodes[_nodes[y].Left].Parent = x;
            }

            // 更新y的父节点
            _nodes[y].Parent = _nodes[x].Parent;

            // 更新x的父节点的子节点
            if (_nodes[x].Parent == NULL_NODE)
            {
                _root = y;
            }
            else if (x == _nodes[_nodes[x].Parent].Left)
            {
                _nodes[_nodes[x].Parent].Left = y;
            }
            else
            {
                _nodes[_nodes[x].Parent].Right = y;
            }

            // 将x设为y的左子节点
            _nodes[y].Left = x;
            _nodes[x].Parent = y;
        }

        /// <summary>
        /// 右旋转
        /// </summary>
        private void RotateRight(int x)
        {
            int y = _nodes[x].Left;

            // 将y的右子节点设为x的左子节点
            _nodes[x].Left = _nodes[y].Right;
            if (_nodes[y].Right != NULL_NODE)
            {
                _nodes[_nodes[y].Right].Parent = x;
            }

            // 更新y的父节点
            _nodes[y].Parent = _nodes[x].Parent;

            // 更新x的父节点的子节点
            if (_nodes[x].Parent == NULL_NODE)
            {
                _root = y;
            }
            else if (x == _nodes[_nodes[x].Parent].Right)
            {
                _nodes[_nodes[x].Parent].Right = y;
            }
            else
            {
                _nodes[_nodes[x].Parent].Left = y;
            }

            // 将x设为y的右子节点
            _nodes[y].Right = x;
            _nodes[x].Parent = y;
        }

        /// <summary>
        /// 用新节点替换旧节点
        /// </summary>
        private void Transplant(int u, int v)
        {
            if (_nodes[u].Parent == NULL_NODE)
            {
                _root = v;
            }
            else if (u == _nodes[_nodes[u].Parent].Left)
            {
                _nodes[_nodes[u].Parent].Left = v;
            }
            else
            {
                _nodes[_nodes[u].Parent].Right = v;
            }

            if (v != NULL_NODE)
            {
                _nodes[v].Parent = _nodes[u].Parent;
            }
        }

        /// <summary>
        /// 查找最小节点
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int Minimum(int x)
        {
            while (_nodes[x].Left != NULL_NODE)
            {
                x = _nodes[x].Left;
            }

            return x;
        }

        /// <summary>
        /// 回收节点
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void RecycleNode(int node)
        {
            // 清空节点数据
            _nodes[node].Key = default;
            _nodes[node].Value = default;
            _nodes[node].Left = NULL_NODE;
            _nodes[node].Parent = NULL_NODE;
            _nodes[node].Color = BLACK;

            // 将节点添加到空闲列表
            _nodes[node].Right = _freeList;
            _freeList = node;
        }

        /// <summary>
        /// 查找最大节点
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int Maximum(int x)
        {
            while (_nodes[x].Right != NULL_NODE)
            {
                x = _nodes[x].Right;
            }

            return x;
        }

        /// <summary>
        /// 获取树中的最小键
        /// </summary>
        public bool TryGetMinKey(out TKey key)
        {
            if (_root == NULL_NODE)
            {
                key = default;
                return false;
            }

            int minNode = Minimum(_root);
            key = _nodes[minNode].Key;
            return true;
        }

        /// <summary>
        /// 获取树中的最大键
        /// </summary>
        public bool TryGetMaxKey(out TKey key)
        {
            if (_root == NULL_NODE)
            {
                key = default;
                return false;
            }

            int maxNode = Maximum(_root);
            key = _nodes[maxNode].Key;
            return true;
        }

        /// <summary>
        /// 获取树中的最小键值对
        /// </summary>
        public bool TryGetMin(out TKey key, out TValue value)
        {
            if (_root == NULL_NODE)
            {
                key = default;
                value = default;
                return false;
            }

            int minNode = Minimum(_root);
            key = _nodes[minNode].Key;
            value = _nodes[minNode].Value;
            return true;
        }

        /// <summary>
        /// 获取树中的最大键值对
        /// </summary>
        public bool TryGetMax(out TKey key, out TValue value)
        {
            if (_root == NULL_NODE)
            {
                key = default;
                value = default;
                return false;
            }

            int maxNode = Maximum(_root);
            key = _nodes[maxNode].Key;
            value = _nodes[maxNode].Value;
            return true;
        }

        /// <summary>
        /// 获取所有键的集合
        /// </summary>
        public List<TKey> GetKeys()
        {
            List<TKey> keys = new List<TKey>(_count);
            if (_root != NULL_NODE)
            {
                CollectKeys(_root, keys);
            }

            return keys;
        }

        /// <summary>
        /// 获取所有键的有序集合
        /// </summary>
        public IEnumerable<TKey> GetKeysSorted()
        {
            return GetKeys().OrderBy(k => k);
        }

        /// <summary>
        /// 收集键
        /// </summary>
        private void CollectKeys(int node, List<TKey> keys)
        {
            if (node == NULL_NODE)
            {
                return;
            }

            CollectKeys(_nodes[node].Left, keys);
            keys.Add(_nodes[node].Key);
            CollectKeys(_nodes[node].Right, keys);
        }

        /// <summary>
        /// 获取所有值的集合
        /// </summary>
        public List<TValue> GetValues()
        {
            List<TValue> values = new List<TValue>(_count);
            if (_root != NULL_NODE)
            {
                CollectValues(_root, values);
            }

            return values;
        }

        /// <summary>
        /// 将红黑树转换为Dictionary
        /// </summary>
        /// <returns>包含相同键值对的Dictionary</returns>
        public Dictionary<TKey, TValue> ToDictionary()
        {
            Dictionary<TKey, TValue> dict = new Dictionary<TKey, TValue>(_count);
            ForEach((key, value) => dict.Add(key, value));
            return dict;
        }

        /// <summary>
        /// 收集值
        /// </summary>
        private void CollectValues(int node, List<TValue> values)
        {
            if (node == NULL_NODE)
            {
                return;
            }

            CollectValues(_nodes[node].Left, values);
            values.Add(_nodes[node].Value);
            CollectValues(_nodes[node].Right, values);
        }

        /// <summary>
        /// 遍历树中的所有键值对
        /// </summary>
        public void ForEach(Action<TKey, TValue> action)
        {
            if (_root == NULL_NODE || action == null)
            {
                return;
            }

            InOrderTraversal(_root, action);
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        private void InOrderTraversal(int node, Action<TKey, TValue> action)
        {
            if (node == NULL_NODE)
            {
                return;
            }

            InOrderTraversal(_nodes[node].Left, action);
            action(_nodes[node].Key, _nodes[node].Value);
            InOrderTraversal(_nodes[node].Right, action);
        }

        /// <summary>
        /// 获取键值对枚举器
        /// </summary>
        public IEnumerable<KeyValuePair<TKey, TValue>> GetEnumerable()
        {
            if (_root != NULL_NODE)
            {
                foreach (var pair in GetEnumerableInternal(_root))
                {
                    yield return pair;
                }
            }
        }

        /// <summary>
        /// 内部枚举方法
        /// </summary>
        private IEnumerable<KeyValuePair<TKey, TValue>> GetEnumerableInternal(int node)
        {
            if (node == NULL_NODE)
            {
                yield break;
            }

            // 中序遍历：左-根-右
            foreach (var pair in GetEnumerableInternal(_nodes[node].Left))
            {
                yield return pair;
            }

            yield return new KeyValuePair<TKey, TValue>(_nodes[node].Key, _nodes[node].Value);

            foreach (var pair in GetEnumerableInternal(_nodes[node].Right))
            {
                yield return pair;
            }
        }

        /// <summary>
        /// 实现IEnumerable<KeyValuePair<TKeyTValue>>接口
        /// </summary>
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return GetEnumerable().GetEnumerator();
        }

        /// <summary>
        /// 实现IEnumerable接口
        /// </summary>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// 索引器 - 允许使用tree[key]语法访问和修改值
        /// </summary>
        public TValue this[TKey key]
        {
            get
            {
                if (TryGetValue(key, out TValue value))
                {
                    return value;
                }

                throw new KeyNotFoundException($"未找到键: {key}");
            }
            set { Add(key, value); }
        }

        /// <summary>
        /// 收缩容量以节省内存
        /// 当实际使用的节点数量远小于容量时，重新分配更小的数组以减少内存占用
        /// </summary>
        public void TrimExcess()
        {
            // 如果实际使用的节点数量小于容量的25%，则收缩数组
            if (_count > 0 && _count < _capacity / 4)
            {
                int newCapacity = Math.Max(_count * 2, DEFAULT_CAPACITY);
                if (newCapacity < _capacity)
                {
                    // 创建新数组并重建树
                    Node[] oldNodes = _nodes;
                    _capacity = newCapacity;
                    _nodes = new Node[_capacity];

                    // 保存所有有效的键值对
                    List<KeyValuePair<TKey, TValue>> pairs = new List<KeyValuePair<TKey, TValue>>(_count);
                    foreach (var pair in GetEnumerable())
                    {
                        pairs.Add(pair);
                    }

                    // 清空树并重新添加所有键值对
                    Clear();
                    foreach (var pair in pairs)
                    {
                        Add(pair.Key, pair.Value);
                    }
                    
                    // 重新分配路径缓存
                    int estimatedMaxDepth = (int)Math.Log(newCapacity, 2) + 1;
                    if (_pathCache.Count < estimatedMaxDepth)
                    {
                        _pathCache.Clear();
                    }
                }
            }
        }

        /// <summary>
        /// 获取指定范围内的所有键值对
        /// </summary>
        /// <param name="fromKey">范围起始键（包含）</param>
        /// <param name="toKey">范围结束键（包含）</param>
        /// <returns>范围内的键值对集合</returns>
        public IEnumerable<KeyValuePair<TKey, TValue>> GetRange(TKey fromKey, TKey toKey)
        {
            if (_root == NULL_NODE) yield break;

            // 确保fromKey <= toKey
            if (fromKey.CompareTo(toKey) > 0)
            {
                TKey temp = fromKey;
                fromKey = toKey;
                toKey = temp;
            }

            // 使用栈进行非递归中序遍历
            Stack<int> stack = new Stack<int>();
            int current = _root;
            bool started = false;

            while (stack.Count > 0 || current != NULL_NODE)
            {
                if (current != NULL_NODE)
                {
                    stack.Push(current);
                    current = _nodes[current].Left;
                }
                else
                {
                    current = stack.Pop();
                    TKey currentKey = _nodes[current].Key;

                    // 如果当前键大于toKey，结束遍历
                    if (currentKey.CompareTo(toKey) > 0)
                    {
                        yield break;
                    }

                    // 如果当前键大于等于fromKey，开始返回结果
                    if (currentKey.CompareTo(fromKey) >= 0)
                    {
                        started = true;
                        yield return new KeyValuePair<TKey, TValue>(currentKey, _nodes[current].Value);
                    }
                    else if (!started && currentKey.CompareTo(fromKey) < 0)
                    {
                        // 继续查找，直到找到大于等于fromKey的节点
                    }

                    current = _nodes[current].Right;
                }
            }
        }

        /// <summary>
        /// 获取大于指定键的最小键
        /// </summary>
        /// <param name="key">参考键</param>
        /// <param name="result">大于参考键的最小键</param>
        /// <returns>是否找到符合条件的键</returns>
        public bool TryGetNextKey(TKey key, out TKey result)
        {
            if (_root == NULL_NODE)
            {
                result = default;
                return false;
            }

            int current = _root;
            int candidate = NULL_NODE;

            while (current != NULL_NODE)
            {
                int comparison = key.CompareTo(_nodes[current].Key);

                if (comparison < 0)
                {
                    // 当前键大于参考键，可能是候选结果
                    candidate = current;
                    current = _nodes[current].Left;
                }
                else
                {
                    // 当前键小于等于参考键，继续向右查找
                    current = _nodes[current].Right;
                }
            }

            if (candidate != NULL_NODE)
            {
                result = _nodes[candidate].Key;
                return true;
            }

            result = default;
            return false;
        }

        /// <summary>
        /// 获取小于指定键的最大键
        /// </summary>
        /// <param name="key">参考键</param>
        /// <param name="result">小于参考键的最大键</param>
        /// <returns>是否找到符合条件的键</returns>
        public bool TryGetPreviousKey(TKey key, out TKey result)
        {
            if (_root == NULL_NODE)
            {
                result = default;
                return false;
            }

            int current = _root;
            int candidate = NULL_NODE;

            while (current != NULL_NODE)
            {
                int comparison = key.CompareTo(_nodes[current].Key);

                if (comparison > 0)
                {
                    // 当前键小于参考键，可能是候选结果
                    candidate = current;
                    current = _nodes[current].Right;
                }
                else
                {
                    // 当前键大于等于参考键，继续向左查找
                    current = _nodes[current].Left;
                }
            }

            if (candidate != NULL_NODE)
            {
                result = _nodes[candidate].Key;
                return true;
            }

            result = default;
            return false;
        }

        /// <summary>
        /// 验证红黑树的属性是否正确
        /// </summary>
        /// <returns>红黑树是否有效</returns>
        public bool IsValid()
        {
            if (_root == NULL_NODE) return true;

            // 验证根节点是黑色
            if (_nodes[_root].Color != BLACK) return false;

            // 验证每条路径上的黑色节点数量相同，且没有连续的红色节点
            int blackCount = -1;
            return ValidateNode(_root, 0, ref blackCount);
        }

        /// <summary>
        /// 验证节点及其子树是否符合红黑树性质
        /// </summary>
        private bool ValidateNode(int node, int blackCountPath, ref int expectedBlackCount)
        {
            if (node == NULL_NODE)
            {
                // 空节点视为黑色
                blackCountPath++;

                // 第一次到达叶子节点，记录黑色节点数量
                if (expectedBlackCount == -1)
                {
                    expectedBlackCount = blackCountPath;
                    return true;
                }

                // 验证黑色节点数量是否一致
                return blackCountPath == expectedBlackCount;
            }

            // 如果当前节点是红色，其子节点必须是黑色
            if (_nodes[node].Color == RED)
            {
                if ((_nodes[node].Left != NULL_NODE && _nodes[_nodes[node].Left].Color == RED) ||
                    (_nodes[node].Right != NULL_NODE && _nodes[_nodes[node].Right].Color == RED))
                {
                    // 存在连续的红色节点，违反了红黑树性质
                    return false;
                }
            }

            // 递归验证左右子树
            if (!ValidateNode(_nodes[node].Left, blackCountPath + (_nodes[node].Color == BLACK ? 1 : 0),
                    ref expectedBlackCount) ||
                !ValidateNode(_nodes[node].Right, blackCountPath + (_nodes[node].Color == BLACK ? 1 : 0),
                    ref expectedBlackCount))
            {
                return false;
            }

            return true;

        }
          /// <summary>
            /// 批量添加键值对
            /// </summary>
            /// <param name="keys">键集合</param>
            /// <param name="values">值集合</param>
            /// <exception cref="ArgumentException">当键集合和值集合长度不一致时抛出</exception>
            public void AddRange(IEnumerable<TKey> keys, IEnumerable<TValue> values)
            {
                if (keys == null) throw new ArgumentNullException(nameof(keys));
                if (values == null) throw new ArgumentNullException(nameof(values));

                using (var keyEnumerator = keys.GetEnumerator())
                using (var valueEnumerator = values.GetEnumerator())
                {
                    while (keyEnumerator.MoveNext())
                    {
                        if (!valueEnumerator.MoveNext())
                        {
                            throw new ArgumentException("键集合和值集合长度不一致");
                        }

                        Add(keyEnumerator.Current, valueEnumerator.Current);
                    }

                    if (valueEnumerator.MoveNext())
                    {
                        throw new ArgumentException("键集合和值集合长度不一致");
                    }
                }
            }

            /// <summary>
            /// 批量移除键
            /// </summary>
            /// <param name="keys">要移除的键集合</param>
            /// <returns>成功移除的键的数量</returns>
            public int RemoveRange(IEnumerable<TKey> keys)
            {
                if (keys == null) throw new ArgumentNullException(nameof(keys));

                int count = 0;
                foreach (var key in keys)
                {
                    if (Remove(key))
                    {
                        count++;
                    }
                }

                return count;
            }

            /// <summary>
            /// 获取树的平衡因子，用于评估树的平衡程度
            /// 返回值越接近1表示树越平衡
            /// </summary>
            /// <returns>平衡因子，范围在0到1之间</returns>
            public double GetBalanceFactor()
            {
                if (_root == NULL_NODE) return 1.0; // 空树视为完全平衡

                int height = Height;
                int nodeCount = _count;

                // 计算完美平衡二叉树在当前高度下的节点数
                int perfectNodeCount = (1 << height) - 1;

                // 计算平衡因子：实际节点数 / 完美平衡树节点数
                // 值越接近1表示树越平衡
                return (double)nodeCount / perfectNodeCount;
            }

        /// <summary>
        /// 重建树以优化结构
        /// 通过重新插入所有节点来创建更平衡的树
        /// </summary>
        public void Rebuild()
        {
            if (_root == NULL_NODE) return;

            // 收集所有键值对
            List<KeyValuePair<TKey, TValue>> pairs = new List<KeyValuePair<TKey, TValue>>(_count);
            ForEach((key, value) => pairs.Add(new KeyValuePair<TKey, TValue>(key, value)));

            // 清空树
            Clear();

            // 对键进行排序
            pairs.Sort((a, b) => a.Key.CompareTo(b.Key));

            // 预分配足够的容量
            EnsureCapacity(pairs.Count);

            // 使用二分插入法重建树
            RebuildBalanced(pairs, 0, pairs.Count - 1);
        }

        /// <summary>
        /// 使用二分插入法重建平衡树
        /// </summary>
        private void RebuildBalanced(List<KeyValuePair<TKey, TValue>> pairs, int start, int end)
        {
            if (start > end) return;

            // 取中间元素作为根节点
            int mid = (start + end) / 2;
            Add(pairs[mid].Key, pairs[mid].Value);

            // 递归处理左右子树
            RebuildBalanced(pairs, start, mid - 1);
            RebuildBalanced(pairs, mid + 1, end);
        }

            #region 序列化支持

            /// <summary>
            /// 将红黑树序列化到流中
            /// </summary>
            /// <param name="stream">目标流</param>
            /// <exception cref="ArgumentNullException">当stream为null时抛出</exception>
            /// <exception cref="SerializationException">序列化失败时抛出</exception>
            public void Serialize(Stream stream)
            {
                if (stream == null) throw new ArgumentNullException(nameof(stream));
                if (!stream.CanWrite) throw new ArgumentException("流不支持写入操作", nameof(stream));

                try
                {
                    // 收集所有有效的键值对
                    List<KeyValuePair<TKey, TValue>> pairs = new List<KeyValuePair<TKey, TValue>>(_count);
                    foreach (var pair in GetEnumerable())
                    {
                        pairs.Add(pair);
                    }

                    // 使用二进制格式化器序列化
                    BinaryFormatter formatter = new BinaryFormatter();
                    formatter.Serialize(stream, pairs);
                }
                catch (Exception ex)
                {
                    throw new SerializationException("序列化红黑树失败", ex);
                }
            }

            /// <summary>
            /// 从流中反序列化红黑树
            /// </summary>
            /// <param name="stream">源流</param>
            /// <exception cref="ArgumentNullException">当stream为null时抛出</exception>
            /// <exception cref="SerializationException">反序列化失败时抛出</exception>
            public void Deserialize(Stream stream)
            {
                if (stream == null) throw new ArgumentNullException(nameof(stream));
                if (!stream.CanRead) throw new ArgumentException("流不支持读取操作", nameof(stream));

                try
                {
                    // 使用二进制格式化器反序列化
                    BinaryFormatter formatter = new BinaryFormatter();
                    var pairs = (List<KeyValuePair<TKey, TValue>>)formatter.Deserialize(stream);

                    // 清空当前树并添加所有键值对
                    Clear();
                    foreach (var pair in pairs)
                    {
                        Add(pair.Key, pair.Value);
                    }
                }
                catch (Exception ex)
                {
                    throw new SerializationException("反序列化红黑树失败", ex);
                }
            }

            /// <summary>
            /// 将红黑树保存到文件
            /// </summary>
            /// <param name="filePath">文件路径</param>
            /// <exception cref="ArgumentNullException">当filePath为null时抛出</exception>
            /// <exception cref="IOException">文件操作失败时抛出</exception>
            /// <exception cref="SerializationException">序列化失败时抛出</exception>
            public void SaveToFile(string filePath)
            {
                if (string.IsNullOrEmpty(filePath)) throw new ArgumentNullException(nameof(filePath));

                using (FileStream fs = new FileStream(filePath, FileMode.Create))
                {
                    Serialize(fs);
                }
            }

            /// <summary>
            /// 从文件加载红黑树
            /// </summary>
            /// <param name="filePath">文件路径</param>
            /// <exception cref="ArgumentNullException">当filePath为null时抛出</exception>
            /// <exception cref="FileNotFoundException">文件不存在时抛出</exception>
            /// <exception cref="IOException">文件操作失败时抛出</exception>
            /// <exception cref="SerializationException">反序列化失败时抛出</exception>
            public void LoadFromFile(string filePath)
            {
                if (string.IsNullOrEmpty(filePath)) throw new ArgumentNullException(nameof(filePath));
                if (!File.Exists(filePath)) throw new FileNotFoundException("指定的文件不存在", filePath);

                using (FileStream fs = new FileStream(filePath, FileMode.Open))
                {
                    Deserialize(fs);
                }
            }

            #endregion
    }
}

  